using ArrayList = System.Collections.ArrayList;

//using CharFormatter				= antlr.CharFormatter;

namespace Spring.Expressions.Parser.antlr.collections.impl;
/*ANTLR Translator Generator
 * Project led by Terence Parr at http://www.jGuru.com
 * Software rights: http://www.antlr.org/license.html
 *
 * $Id:$
 */

//
// ANTLR C# Code Generator by Micheal Jordan
//                            Kunle Odutola       : kunle UNDERSCORE odutola AT hotmail DOT com
//                            Anthony Oguntimehin
//
// With many thanks to Eric V. Smith from the ANTLR list.
//
/*A BitSet to replace java.util.BitSet.
 * Primary differences are that most set operators return new sets
 * as opposed to oring and anding "in place".  Further, a number of
 * operations were added.  I cannot contain a BitSet because there
 * is no way to access the internal bits (which I need for speed)
 * and, because it is final, I cannot subclass to add functionality.
 * Consider defining set degree.  Without access to the bits, I must
 * call a method n times to test the ith bit...ack!
 *
 * Also seems like or() from util is wrong when size of incoming set is bigger
 * than this.bits.length.
 *
 * @author Terence Parr
 * @author <br><a href="mailto:pete@yamuna.demon.co.uk">Pete Wells</a>
 */

public class BitSet : ICloneable
{
    protected internal const int BITS = 64; // number of bits / long
    protected internal const int NIBBLE = 4;
    protected internal const int LOG_BITS = 6; // 2^6 == 64

    /*We will often need to do a mod operator (i mod nbits).  Its
     * turns out that, for powers of two, this mod operation is
     * same as (i & (nbits-1)).  Since mod is slow, we use a
     * precomputed mod mask to do the mod instead.
     */
    protected internal static readonly int MOD_MASK = BITS - 1;

    /*The actual data bits */
    protected internal long[] dataBits;

    /*Construct a bitset of size one word (64 bits) */
    public BitSet() : this(BITS)
    {
    }

    /*Construction from a static array of longs */
    public BitSet(long[] bits_)
    {
        dataBits = bits_;
    }

    /*Construct a bitset given the size
     * @param nbits The size of the bitset in bits
     */
    public BitSet(int nbits)
    {
        dataBits = new long[((nbits - 1) >> LOG_BITS) + 1];
    }

    /*or this element into this set (grow as necessary to accommodate) */
    public virtual void add(int el)
    {
        int n = wordNumber(el);
        if (n >= dataBits.Length)
        {
            growToInclude(el);
        }

        dataBits[n] |= bitMask(el);
    }

    public virtual BitSet and(BitSet a)
    {
        BitSet s = (BitSet) this.Clone();
        s.andInPlace(a);
        return s;
    }

    public virtual void andInPlace(BitSet a)
    {
        int min = (int) (Math.Min(dataBits.Length, a.dataBits.Length));
        for (int i = min - 1; i >= 0; i--)
        {
            dataBits[i] &= a.dataBits[i];
        }

        // clear all bits in this not present in a (if this bigger than a).
        for (int i = min; i < dataBits.Length; i++)
        {
            dataBits[i] = 0;
        }
    }

    private static long bitMask(int bitNumber)
    {
        int bitPosition = bitNumber & MOD_MASK; // bitNumber mod BITS
        return 1L << bitPosition;
    }

    public virtual void clear()
    {
        for (int i = dataBits.Length - 1; i >= 0; i--)
        {
            dataBits[i] = 0;
        }
    }

    public virtual void clear(int el)
    {
        int n = wordNumber(el);
        if (n >= dataBits.Length)
        {
            // grow as necessary to accommodate
            growToInclude(el);
        }

        dataBits[n] &= ~ bitMask(el);
    }

    public virtual object Clone()
    {
        BitSet s;
        try
        {
            s = new BitSet();
            s.dataBits = new long[dataBits.Length];
            Array.Copy(dataBits, 0, s.dataBits, 0, dataBits.Length);
        }
        catch //(System.Exception e)
        {
            throw new System.ApplicationException();
        }

        return s;
    }

    public virtual int degree()
    {
        int deg = 0;
        for (int i = dataBits.Length - 1; i >= 0; i--)
        {
            long word = dataBits[i];
            if (word != 0L)
            {
                for (int bit = BITS - 1; bit >= 0; bit--)
                {
                    if ((word & (1L << bit)) != 0)
                    {
                        deg++;
                    }
                }
            }
        }

        return deg;
    }

    override public int GetHashCode()
    {
        return dataBits.GetHashCode();
    }

    /*code "inherited" from java.util.BitSet */
    override public bool Equals(object obj)
    {
        if ((obj != null) && (obj is BitSet))
        {
            BitSet bset = (BitSet) obj;

            int n = (int) (System.Math.Min(dataBits.Length, bset.dataBits.Length));
            for (int i = n; i-- > 0;)
            {
                if (dataBits[i] != bset.dataBits[i])
                {
                    return false;
                }
            }

            if (dataBits.Length > n)
            {
                for (int i = (int) (dataBits.Length); i-- > n;)
                {
                    if (dataBits[i] != 0)
                    {
                        return false;
                    }
                }
            }
            else if (bset.dataBits.Length > n)
            {
                for (int i = (int) (bset.dataBits.Length); i-- > n;)
                {
                    if (bset.dataBits[i] != 0)
                    {
                        return false;
                    }
                }
            }

            return true;
        }

        return false;
    }

    /*
     * Grows the set to a larger number of bits.
     * @param bit element that must fit in set
     */
    public virtual void growToInclude(int bit)
    {
        int newSize = (int) (System.Math.Max(dataBits.Length << 1, numWordsToHold(bit)));
        long[] newbits = new long[newSize];
        Array.Copy(dataBits, 0, newbits, 0, dataBits.Length);
        dataBits = newbits;
    }

    public virtual bool member(int el)
    {
        int n = wordNumber(el);
        if (n >= dataBits.Length)
            return false;
        return (dataBits[n] & bitMask(el)) != 0;
    }

    public virtual bool nil()
    {
        for (int i = dataBits.Length - 1; i >= 0; i--)
        {
            if (dataBits[i] != 0)
                return false;
        }

        return true;
    }

    public virtual BitSet not()
    {
        BitSet s = (BitSet) this.Clone();
        s.notInPlace();
        return s;
    }

    public virtual void notInPlace()
    {
        for (int i = dataBits.Length - 1; i >= 0; i--)
        {
            dataBits[i] = ~ dataBits[i];
        }
    }

    /*complement bits in the range 0..maxBit. */
    public virtual void notInPlace(int maxBit)
    {
        notInPlace(0, maxBit);
    }

    /*complement bits in the range minBit..maxBit.*/
    public virtual void notInPlace(int minBit, int maxBit)
    {
        // make sure that we have room for maxBit
        growToInclude(maxBit);
        for (int i = minBit; i <= maxBit; i++)
        {
            int n = wordNumber(i);
            dataBits[n] ^= bitMask(i);
        }
    }

    private int numWordsToHold(int el)
    {
        return (el >> LOG_BITS) + 1;
    }

    public static BitSet of(int el)
    {
        BitSet s = new BitSet(el + 1);
        s.add(el);
        return s;
    }

    /*return this | a in a new set */
    public virtual BitSet or(BitSet a)
    {
        BitSet s = (BitSet) this.Clone();
        s.orInPlace(a);
        return s;
    }

    public virtual void orInPlace(BitSet a)
    {
        // If this is smaller than a, grow this first
        if (a.dataBits.Length > dataBits.Length)
        {
            setSize((int) (a.dataBits.Length));
        }

        int min = (int) (System.Math.Min(dataBits.Length, a.dataBits.Length));
        for (int i = min - 1; i >= 0; i--)
        {
            dataBits[i] |= a.dataBits[i];
        }
    }

    // remove this element from this set
    public virtual void remove(int el)
    {
        int n = wordNumber(el);
        if (n >= dataBits.Length)
        {
            growToInclude(el);
        }

        dataBits[n] &= ~ bitMask(el);
    }

    /*
     * Sets the size of a set.
     * @param nwords how many words the new set should be
     */
    private void setSize(int nwords)
    {
        long[] newbits = new long[nwords];
        int n = (int) (System.Math.Min(nwords, dataBits.Length));
        Array.Copy(dataBits, 0, newbits, 0, n);
        dataBits = newbits;
    }

    public virtual int size()
    {
        return dataBits.Length << LOG_BITS; // num words * bits per word
    }

    /*return how much space is being used by the dataBits array not
     *  how many actually have member bits on.
     */
    public virtual int lengthInLongWords()
    {
        return dataBits.Length;
    }

    /*Is this contained within a? */
    public virtual bool subset(BitSet a)
    {
        if (a == null) //(a == null || !(a is BitSet))
            return false;
        return this.and(a).Equals(this);
    }

    /*Subtract the elements of 'a' from 'this' in-place.
     * Basically, just turn off all bits of 'this' that are in 'a'.
     */
    public virtual void subtractInPlace(BitSet a)
    {
        if (a == null)
            return;
        // for all words of 'a', turn off corresponding bits of 'this'
        for (int i = 0; i < dataBits.Length && i < a.dataBits.Length; i++)
        {
            dataBits[i] &= ~ a.dataBits[i];
        }
    }

    public virtual int[] toArray()
    {
        int[] elems = new int[degree()];
        int en = 0;
        for (int i = 0; i < (dataBits.Length << LOG_BITS); i++)
        {
            if (member(i))
            {
                elems[en++] = i;
            }
        }

        return elems;
    }

    public virtual long[] toPackedArray()
    {
        return dataBits;
    }

    override public string ToString()
    {
        return ToString(",");
    }

    /*Transform a bit set into a string by formatting each element as an integer
     * @separator The string to put in between elements
     * @return A commma-separated list of values
     */
    public virtual string ToString(string separator)
    {
        string str = "";
        for (int i = 0; i < (dataBits.Length << LOG_BITS); i++)
        {
            if (member(i))
            {
                if (str.Length > 0)
                {
                    str += separator;
                }

                str = str + i;
            }
        }

        return str;
    }

    /*Create a string representation where instead of integer elements, the
     * ith element of vocabulary is displayed instead.  Vocabulary is a Vector
     * of Strings.
     * @separator The string to put in between elements
     * @return A commma-separated list of character constants.
     */
    public virtual string ToString(string separator, ArrayList vocabulary)
    {
        if (vocabulary == null)
        {
            return ToString(separator);
        }

        string str = "";
        for (int i = 0; i < (dataBits.Length << LOG_BITS); i++)
        {
            if (member(i))
            {
                if (str.Length > 0)
                {
                    str += separator;
                }

                if (i >= vocabulary.Count)
                {
                    str += "<bad element " + i + ">";
                }
                else if (vocabulary[i] == null)
                {
                    str += "<" + i + ">";
                }
                else
                {
                    str += (string) vocabulary[i];
                }
            }
        }

        return str;
    }

    /*
     * Dump a comma-separated list of the words making up the bit set.
     * Split each 64 bit number into two more manageable 32 bit numbers.
     * This generates a comma-separated list of C++-like unsigned long constants.
     */
    public virtual string toStringOfHalfWords()
    {
        string s = new string("".ToCharArray());
        for (int i = 0; i < dataBits.Length; i++)
        {
            if (i != 0)
                s += ", ";
            long tmp = dataBits[i];
            tmp &= 0xFFFFFFFFL;
            s += (tmp + "UL");
            s += ", ";
            tmp = SupportClass.URShift(dataBits[i], 32);
            tmp &= 0xFFFFFFFFL;
            s += (tmp + "UL");
        }

        return s;
    }

    /*
     * Dump a comma-separated list of the words making up the bit set.
     * This generates a comma-separated list of Java-like long int constants.
     */
    public virtual string toStringOfWords()
    {
        string s = new string("".ToCharArray());
        for (int i = 0; i < dataBits.Length; i++)
        {
            if (i != 0)
                s += ", ";
            s += (dataBits[i] + "L");
        }

        return s;
    }

    /*Print out the bit set but collapse char ranges. */
/*		public virtual string toStringWithRanges(string separator, CharFormatter formatter)
        {
            string str = "";
            int[] elems = this.toArray();
            if (elems.Length == 0)
            {
                return "";
            }
            // look for ranges
            int i = 0;
            while (i < elems.Length)
            {
                int lastInRange;
                lastInRange = 0;
                 for (int j = i + 1; j < elems.Length; j++)
                {
                    if (elems[j] != elems[j - 1] + 1)
                    {
                        break;
                    }
                    lastInRange = j;
                }
                // found a range
                if (str.Length > 0)
                {
                    str += separator;
                }
                if (lastInRange - i >= 2)
                {
                    str += formatter.literalChar(elems[i]);
                    str += "..";
                    str += formatter.literalChar(elems[lastInRange]);
                    i = lastInRange; // skip past end of range for next range
                }
                else
                {
                    // no range, just print current char and move on
                    str += formatter.literalChar(elems[i]);
                }
                i++;
            }
            return str;
        }
*/
    private static int wordNumber(int bit)
    {
        return bit >> LOG_BITS; // bit / BITS
    }
}